package org.example.myleet.p676;

public class MagicDictionary {

    MyTrieTree trieTree;

    public MagicDictionary() {
        trieTree = new MyTrieTree();
    }

    public void buildDict(String[] dictionary) {
        for (String word : dictionary) {
            trieTree.add(word);
        }
    }

    public boolean search(String searchWord) {
        return trieTree.searchWord(searchWord, 0, null, false);
    }

    static class MyTrieTree implements TrieTree {
        TrieNode root;

        public MyTrieTree() {
            root = new TrieNode('0');
        }

        @Override
        public void add(String word) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); ++i) {
                char c = word.charAt(i);
                int idx = c - 'a';
                if (null == cur.children[idx]) {
                    cur.children[idx] = new TrieNode(c);
                }
                cur = cur.children[idx];
            }
            cur.end = true;
        }

        public boolean searchWord(String word, int i, TrieNode node, boolean replaced) {
            if (null == node) {
                return searchWord(word, i, root, replaced);
            }
            if (i >= word.length()) {
                //到达单词尾部，如果已经替换过字母，且字典树中确实找到这样的单词结尾，才能true
                return replaced && node.end;
            }
            char w = word.charAt(i);
            TrieNode[] children = node.children;
            boolean found = false;
            int iNext = i + 1;
            char c;
            for (int j = 0; j < 26; ++j) {
                c = (char) (j + 'a');
                if (null != children[j]) {
                    if (w != c && replaced) {
                        //如果w != c，且已经替换过一个字母，则一定是通过替换一个字母也找不到的单词
                        continue;
                    }
                    //如果w == c，继续DFS搜索；否则，标记为替换了一个字母的DFS搜索
                    if (searchWord(word, iNext, children[j], w == c ? replaced : true)) {
                        //只要找到一个匹配就行
                        found = true;
                        break;
                    }
                }
            }
            return found;
        }
    }

    static class TrieNode {
        TrieNode[] children;
        boolean end;
        char c;

        public TrieNode(char c) {
            this.c = c;
            end = false;
            children = new TrieNode[26];
        }
    }

    interface TrieTree {

        /**
         * 向字典树添加一个单词
         */
        void add(String word);
    }
}
